package leetcode.datastructures.linkedlist;

import java.util.Stack;

/**
 * @author shilei
 * @create 2021-10-08 17:40
 * 单链表演示案例
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        HeroNode node1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node4 = new HeroNode(4, "林冲", "豹子头");
        SingleLinkedList linkedList = new SingleLinkedList();
        //添加有顺序的
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node3);

//        //测试 单链表的反转
//        System.out.println("没反转之前链表：");
//        linkedList.showList();
//        reverseList(linkedList.getHead());
//        System.out.println("反转之后的链表：");
//        linkedList.showList();

        //测试 单链表逆序打印
        System.out.println("没反转之前链表：");
        linkedList.showList();
        System.out.println("反转之后的链表：");
        reversePrint(linkedList.getHead());


        //无顺序的
//        linkedList.add(node1);
//        linkedList.add(node2);
//        linkedList.add(node3);
//        linkedList.add(node4);
//        linkedList.showList();
//
//        HeroNode heroNode = new HeroNode(4, "林冲~~", "豹子头~~");
//        linkedList.update(heroNode);
//        System.out.println("修改后的链表：");
//        linkedList.showList();
//
//        linkedList.delete(1);
//        linkedList.delete(4);
//        System.out.println("删除后的链表：");
//        linkedList.showList();
//
//        //单链表中有效节点的个数
//        System.out.println(getLength(linkedList.getHead()));
//
//
//        HeroNode lastIndexNode = findLastIndexNode(linkedList.getHead(), 3);
//        System.out.println(lastIndexNode);

    }

    /**
     * 单链表逆序打印
     * 方式1 先将单链表进行反转操作，然后在遍历即可，不推荐-因为这样会改变单链表原来的数据结构
     * 方式2 利用栈这个数据结构 将各个节点压入栈中，然后利用栈的先进后出 的特点 就实现了逆序打印效果
     *
     */
    public static void reversePrint(HeroNode head) {
        //如果当前链表为空 不需要打印
        if (head.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next; //后移
        }
        while (stack.size() > 0 ){
            System.out.println(stack.pop());
        }
    }

    /**
     * 单链表的翻转
     * 思路：
     *  1、先定义一个节点 reverseHead = new HeroNode()
     *  2、从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
     *  3、原来的链表 head.next = reverseHead.next 完成反转
     */
    public static void reverseList(HeroNode head) {
        //如果当前链表为空 或者只有一个节点则直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助的指针（变量）帮助我们来遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null; //指向当前节点【cur】的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
        while (cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            //将当前节点指向链表
            reverseHead.next = cur;
            cur = next;//让 cur 后移
        }
        //将head.next 指向 reverseHead.next 实现单链表翻转
        head.next = reverseHead.next;

    }



    /**
     * 求单链表中有效节点的个数(如果是带头节点的链表 需求不统计头节点)
     *
     * @param head 链表的头节点
     * @return 返回有效个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;//空链表
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 查找单链表中倒数第K个节点
     * 思路：
     * 1、编写一个方法接收 head 节点，同时接收一个 index
     * 2、index 表示是倒数第 index 个节点
     * 3、先把链表从头到尾遍历，得到链表的总长度 getLength
     * 4、得到size 后，我们从链表的第一个开始遍历 （size-index）个 就可以得到
     * 5、如果找到 返回节点 未找到 返回null
     */
    public static  HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        //第一个遍历得到长度
        int size = getLength(head);
        //第二个遍历得到 size-index 位置，就是我们倒数的第K个节点
        //校验index 的合法性
        if (index <= 0 || index > size) {
            return null;
        }
        //定义辅助变量 进行循环
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

//定义链表
class SingleLinkedList {
    //先初始化一个头节点 头节点不用动 不存放具体数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    //添加节点到单项链表
    //思路 当不考虑顺序时
    //1.找到当前链表的最后一个节点
    //2.将最后这个节点的 next 指向新的节点
    public void add(HeroNode heroNode) {
        //因为 head 节点不能动 所以我们需要一个辅助变量 temp
        HeroNode temp = head;
        //遍历链表找到最后节点 为null的节点数据
        while (true) {
            //当为空时结束循环
            if (temp.next == null) {
                break;
            }
            //如果没有找到将temp后移
            temp = temp.next;
        }
        //当退出 while 循环时  temp 就指向了最后节点 将最后节点指向新的节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果这个排名存在 则添加失败 给出提示
    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动 所以需要给一个辅助指针来帮忙找到添加的位置
        //因为单链表 因为我们找到 temp 是位于添加位置的前一个节点 否则插入不了
        HeroNode temp = head;
        boolean flag = false;//flag 标志为当前添加是否存在 默认不存在
        while (true) {
            if (temp.next == null) {//说明temp已经在链表最后
                break;
            }
            if (temp.next.no > heroNode.no) {//位置找到 就在temp 后面
                break;
            } else if (temp.next.no == heroNode.no) {//说明需要添加的已经存在
                flag = true;
                break;
            }
            //后移 相当于遍历链表
            temp = temp.next;
        }
        if (flag) {
            //如果存在则说明不允许插入
            System.out.printf("准备插入的英雄编号 %d 已经存在\n", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息 根据 no 来修改
    public void update(HeroNode heroNode) {
        if (head.next == null) {
            System.out.println("链表为空~~");
            return;
        }
        //找到需要修改的节点根据no来修改
        //需要一个辅助变量指针
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while (true) {
            if (temp == null) {
                break;//已经变量完节点
            }
            if (temp.no == heroNode.no) {
                flag = true;//找到节点 进行修改
                break;
            }
            temp = temp.next;
        }
        //根据 flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.println("没找到对应节点");
        }
    }

    //删除当前节点对应的节点  需要临时变量做辅助指针
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;//标志位  标志是否找到要删除的节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                //说明找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //说明找到进行删除
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到需要删除的节点");
        }

    }

    //显示链表[遍历]
    public void showList() {
        //判断当前链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);

            //将temp 后移  防止死循环 打印下一个节点
            temp = temp.next;

        }
    }

}

//定义 HeroNode 每一个 HeroNode 对象就是一个节点
class HeroNode {

    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode [no = " + no + ", name = " + name + ", nickName = " + nickName + "]";
    }
}